package com.leetcode.根据算法进行分类.二分查找相关;

/**
 * @author: xiaomi
 * @date: 2021/3/6
 * @description: 50. Pow(x, n)
 * https://leetcode-cn.com/leetbook/read/programmation-efficace/9bl7w3/
 */
public class LC50_Powxn {

    static LC50_Powxn action = new LC50_Powxn();

    public static void main(String[] args) {
        test1();
    }

    static void test1() {
        //
        double x = 2;
        int n = 10;
        double res = action.myPow(x, n);
        System.out.println(res);
    }


    /**
     * 还需要注意复数时，转为正数的数组越界问题
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        if (n < 0) {
            long m = n;
            return 1 / quickPow(x, -m);
        }
        return quickPow(x, n);
    }

    private double quickPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double cur = x;
        double left = 1;
        while (n > 1) {
            if ((n & 1) == 1) {
                //奇数
                left *= cur;
            }
            cur *= cur;
            n = n >> 1;
        }
        return left * cur;
    }

    //居然栈溢出了
    private double quickPowByRecursive(double x, int n) {
        if (n == 0) {
            return 1;
        }
        int m = n >> 1;
        //保存避免重复计算
        double y = quickPowByRecursive(x, m);
        if ((n & 1) == 1) {
            //奇数
            return x * y * y;
        } else {
            return y * y;
        }

    }


}
